package de.fhbrs.sort;

import fedora.server.types.gen.ObjectFields;

public class QuickSort
{
  private Compare delegate;
  private ObjectFields [] userArray;
  
  public static void sort( ObjectFields [] userArray, Compare delegate )
  {
    QuickSort h = new QuickSort();
    h.delegate = delegate;
    h.userArray = userArray;
    if( h.isAlreadySorted() )
      return;
    h.quicksort( 0, userArray.length-1 );
    return;
  }

  private void quicksort( int p, int r )
  {
    if ( p < r ) {
      int q = partition( p, r );
      if ( q == r )
        q--;
      quicksort( p, q );
      quicksort( q+1, r );
    }
  }

  private int partition( int lo, int hi )
  {
	ObjectFields pivot = userArray[lo];
    while ( true ) {
      while ( delegate.compare( userArray[hi],pivot) >= 0 && lo < hi )
        hi--;
      while ( delegate.compare( userArray[lo],pivot) < 0 && lo < hi )
        lo++;
      if (lo < hi) {
    	ObjectFields T = userArray[lo];
        userArray[lo] = userArray[hi];
        userArray[hi] = T;
        }
      else return hi;
    }
  }

  private boolean isAlreadySorted()
  {
    for ( int i=1; i<userArray.length; i++ )
      if ( delegate.compare( userArray[i], userArray[i-1]) < 0 )
      return false;
   return true;
  }
}